package leetcode;
/**
 * 面试题02.04.分割链表
 * 给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有小于x的节点都出现在 大于或等于 x 的节点之前。
 * 你不需要保留每个分区中各节点的初始相对位置。
 * 输入：head = [1,4,3,2,5,2], x = 3
 * 输出：[1,2,2,4,3,5]
 */
public class Interview_0204 {
    /** 创建一大一小两个链表，再拼接 **/
    //x是用户输入的定值，并不是第x个节点的值
    public ListNode partition(ListNode head, int x) {
        //创建两个链表，并设置虚拟头节点
        ListNode smallHead = new ListNode(-101);
        ListNode bigHead = new ListNode(-101);
        //暂存两个头节点，以防跑丢
        ListNode smallNode = smallHead;
        ListNode bigNode = bigHead;
        //遍历传入的head链表
        while(head != null){
            if(head.val < x){
                //把小于x的节点尾接在small链表后
                smallNode.next = head;
                //smallNode向后移一位
                smallNode = smallNode.next;
                //相当于 smallNode = head;
            }else{
                //把大于等于x的节点尾接在big链表后
                bigNode.next = head;
                bigNode = bigNode.next;
            }
            head = head.next;
        }
        //把大值链表接在小值链表的后面
        smallNode.next = bigHead.next;
        //大值链表的最后一个大值节点指向null，以防出现 -> 5 -> 2 -> null 的情况
        bigNode.next = null;
        return smallHead.next;
    }
}
